我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode.cn/problems/min-stack/

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MinStack {
    stack<int> stackA;
    stack<int> stackB;
public:
    MinStack() {
    }
    
    void push(int val) {
        stackA.push(val);
        if (stackB.empty())
            stackB.push(val);
        else
            stackB.push(min(stackB.top(), val));
    }
    
    void pop() {
        stackA.pop();
        stackB.pop();
    }
    
    int top() {
        return stackA.top();
    }
    
    int getMin() {
        return stackB.top();
    }
};

思路

主要难点还是能随时获取到栈中的最小元素

我们可以建立一个新的栈B用来存放最小元素，每当我们往主栈（栈A）push元素的时候，同时把这个元素跟栈B中的top元素进行比较，然后在B中push进二者较小的那个，这样就能够保证B中top的元素永远是最小的元素

有一个要点就是当我们存放第一个元素的时候，此时的stackB为空，自然无法调用stackB.top()，所以我们需要判断是否是初始化后第一次往栈中push元素。可以用stackB.empty()方法判断栈B是否为空。

官方题解用了在构造函数中首先往B中push一个东西来达到相同的效果

1
2
3
MinStack() {
		min_stack.push(INT_MAX);
}

虽然我暂时不太明白INT_MAX的意思（菜